package top.fengleifeng.question;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import top.fengleifeng.util.Constants;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年12月11日 11:18 上午
 */
public class Num442数组中重复的数据 {


    class Solution {

        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new LinkedList<>();
            Set<Integer> resultSet = new HashSet<>();
            int length = nums.length;
            if (length <= 0) {
                return result;
            }
            int index = 0;
            while (index < length) {
                int indexValue = index + 1;
                int nowValue = nums[index];
                if (nowValue == -1) {
                    index++;
                    continue;
                }
                if (nowValue == indexValue) {
                    index++;
                    continue;
                } else {
                    int nowNeedIndex = nowValue - 1;
                    int nowNeddIndexValue = nums[nowNeedIndex];
                    if (nowNeddIndexValue == nowValue) {//说明有重复了 相同
                        nums[index] = -1;
                        index++;
                        resultSet.add(nowValue);
                    } else {//不相同
                        int temp = nowValue;
                        nums[index] = nowNeddIndexValue;
                        nums[nowNeedIndex] = temp;
                    }
                }
            }
            result.addAll(resultSet);
            return result;
        }
    }


//    class Solution {
//        public List<Integer> findDuplicates(int[] nums) {
//            List<Integer> result = new LinkedList<>();
//            for (int i = 0; i < nums.length; i++) {
//                int num = Math.abs(nums[i]);
//                int value = nums[num-1];
//                if(value<0){
//                    if (result.contains(num)) {
//                        continue;
//                    } else {
//                        result.add(num);
//                    }
//                }else{
//                    nums[num-1] = -nums[num-1];
//                }
//            }
//            return result;
//        }
//    }

    public static void main(String[] args) {
        int[] ints = {4, 3, 2, 7, 8, 2, 3, 1};
//        int[] ints = {4, 3, 2, 7, 8, 2, 3, 1,5,7,2,11,15,11,12,5,3};
        List<Integer> duplicates = new Num442数组中重复的数据().new Solution().findDuplicates(ints);
        Constants.pringLinkedList(duplicates);
    }
}
